from collections import deque


#二叉树的序列化与反序列化, 先序遍历方式
class Node :
    def __init__(self, data: int):
        self.value = data
        self.left = None
        self.right = None

def serialByPre(head: None) -> str:
    if not head: return '#_'
    res = f'{head.value}' + '_'
    res += serialByPre(head.left)
    res += serialByPre(head.right)
    return res



def reconPreOrder(queue: deque)  -> Node:
    value = queue.popleft()
    if '#' in value: return None
    head = Node(int(value))
    head.left = reconPreOrder(queue)
    head.right = reconPreOrder(queue)
    return head
# 反序列化之前先把节点放入队列
def reconByPreString(preStr: str) -> Node:
    values = preStr.split('_', preStr.count('_') - 1)    # values.count('!') - 1  去除list里面的最后一个空元素
    queue = deque()
    for i in values:
        queue.append(i)
    return reconPreOrder(queue)  # 调用反序列化函数


# 按层序列化
def serialByLevel(head: Node ) -> str:
    if not head: return "#_"
    res = f'{head.value}' + "_"
    queue = deque()
    queue.append(head)
    while len(queue) > 0:
        head = queue.popleft()
        if head.left :
            res += f'{head.left.value}' + "_"
            queue.append(head.left)
        else : #如果为None 只序列化不加队列
            res += "#_"
        if head.right:
            res += f'{head.right.value}' + "_"
            queue.append(head.right)
        else :
            res += "#_"
    return res

# 按层反序列化
def generateNodeByString(val: str) -> Node:
    if val == "#": return None
    return Node(int(val))

def reconByLevelString(levelStr: str) -> Node:
    values = levelStr.split('_')
    index = 0
    head = generateNodeByString(values[index])
    index += 1
    queue = deque()
    if head : queue.append(head)
    while len(queue) > 0:
        node = queue.popleft()
        node.left = generateNodeByString(values[index])
        index += 1
        node.right = generateNodeByString(values[index])
        index += 1
        if node.left  :
            queue.append(node.left)
        if node.right :
            queue.append(node.right)
    return head

# for test -- print tree

def getSpace(num: int) -> str:
    # return f'|{" "*num}|'
    return f'|{" "*num}|'

def printInOrder(head: Node, height: int, to: int, length: int):
    if not head :  return
    printInOrder(head.right, height + 1, "v", length)
    val = to + str(head.value) + to
    lenM = len(val)
    lenL = (length-lenM) >> 1
    lenR = length - lenM - lenL
    val = getSpace(lenL) + val + getSpace(lenR)
    print(getSpace(height * length) + val)
    printInOrder(head.left, height + 1, "^", length)


def printTree(head: Node) :
    print("Binary Tree:")
    printInOrder(head, 0, "H", length=17)

def main():
    head = None
    printTree(head)
    pre = serialByPre(head)
    print("serialize tree by pre-order: " + pre)
    head = reconByPreString(pre)
    print("reconstruct tree by pre-order, ")
    printTree(head)
    level = serialByLevel(head)
    print("serialize tree by level: " + level)
    head = reconByLevelString(level)
    print("reconstruct tree by level, ")
    printTree(head)  
    print("====================================")
    head = Node(1)
    printTree(head)   
    pre = serialByPre(head)
    print("serialize tree by pre-order: " + pre)
    head = reconByPreString(pre)
    print("reconstruct tree by pre-order, ")
    printTree(head)  
    level = serialByLevel(head)
    print("serialize tree by level: " + level)
    head = reconByLevelString(level)
    print("reconstruct tree by level, ")
    printTree(head) 
    print("====================================")
    head =  Node(1)
    head.left =  Node(2)
    head.right =  Node(3)
    head.left.left =  Node(4)
    head.right.right =  Node(5)
    printTree(head)  
    pre = serialByPre(head)
    print("serialize tree by pre-order: " + pre)
    head = reconByPreString(pre)
    print("reconstruct tree by pre-order, ")
    printTree(head)
    level = serialByLevel(head)
    print("serialize tree by level: " + level)
    head = reconByLevelString(level)
    print("reconstruct tree by level, ")
    printTree(head)
    print("====================================")
    head =  Node(100)
    head.left =  Node(21)
    head.left.left =  Node(37)
    head.right =  Node(-42)
    head.right.left =  Node(0)
    head.right.right =  Node(666)
    printTree(head)
    pre = serialByPre(head)
    print("serialize tree by pre-order: " + pre)
    head = reconByPreString(pre)
    print("reconstruct tree by pre-order, ")
    printTree(head)  
    level = serialByLevel(head)
    print("serialize tree by level: " + level)
    head = reconByLevelString(level)
    print("reconstruct tree by level, ")
    printTree(head)   
    print("====================================")
main()